Network virtualization (NV) has evolved into a key enabling technology for offering next generation network services. Network virtualization requires efficient mapping of a virtual network (VN) to a substrate network (SN), which is also referred to as virtual network embedding (VNE).
Failure of network elements (both nodes and links) may occur at any time, yet many network operators have a desire for high availability networks. As deployments of network virtualization in production/commercial-grade networks using commodity hardware increase, failures in the underlying substrate network are even more common, and virtual network embedding has to tackle such failures to ensure virtual network survivability.
In the case of failures in the substrate network, one may end up with multiple virtual node and virtual link failures, affecting numerous virtual networks at a time. When re-embedding several virtual networks, the combinatorial possibilities available make the task of finding the most efficient mapping challenging. Clearly, therefore, providers of virtual networks would welcome more efficient and scalable re-mapping algorithms responsive to failures of, in particular, substrate nodes.